/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2024-11-26
 * Time: 23:26
 */
public class test3 {
    /*
    LeetCode 面试题 17.19 消失的两个数字
    给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？

    以任意顺序返回这两个数字均可。
     */
    public int[] missingTwo(int[] nums) {
        // 1.先将两个数组都进行异或
        int tmp = 0;
        for(int x:nums){
            tmp ^=x;
        }
        for(int i =1;i<=nums.length+2;i++){
            tmp ^=i;
        }
        // 2. 找到这两个数字异或后第一个为1的地方（diff）
        int diff = 0;
        while(true){
            if( ((tmp>>diff) &1) == 1 ){
                break;
            }else{
                diff++;
            }
        }
        // 3. 将所有数字的diff位分为两类，一类为0，一类为1
        int[] ret = new int[2];
        for(int x:nums){
            if( ((x>>diff) &1) ==1){
                ret[1] ^=x;
            }else{
                ret[0] ^=x;
            }
        }
        for(int i=1;i<=nums.length+2;i++){
            if( ((i>>diff) &1) ==1){
                ret[1] ^=i;
            }else{
                ret[0] ^=i;
            }
        }
        return ret;
    }
}
